#include <cassert>
#include <iostream>
#include <vector>

template <typename T> void swap(T &t1, T &t2) {
  T t = t1;
  t1 = t2;
  t2 = t;
}

// 快速排序函数
template <typename T> int partition(std::vector<T> &v, int start, int end) {
  int i = start + 1, j = end;
  while (i < j) {
    while (i < j && v[j] >= v[start])
      j--;
    while (i < j && v[i] <= v[start])
      i++;
    swap(v[i], v[j]);
  }
  swap(v[start], v[i]);
  assert(i == j);
  return i;
}

/* 快速排序 */
template <typename T> void quick_sort(std::vector<T> &v, int left, int right) {
  // 子数组长度为 1 时终止递归
  if (left >= right)
    return;
  // 哨兵划分
  int pivot = partition(v, left, right);
  // 递归左子数组、右子数组
  quick_sort(v, left, pivot - 1);
  quick_sort(v, pivot + 1, right);
}

int main() {
  std::vector<int> list = {9, 8, 6, 4, 5, 3, 1, 2};
  //   std::vector<int> list = {9, 8, 7, 6, 5, 4, 3, 2, 1};
  quick_sort<int>(list, 0, list.size() - 1);
  for (int i = 0; i < list.size(); i++)
    std::cout << list[i];
  std::cout << std::endl;
  return 0;
}